// Source : https://leetcode.com/problems/4sum/
// Author : simba
// Date   : 2016-06-08

package main

import (
	"fmt"
	"sort"
)

func fourSum(nums []int, target int) [][]int {
	var result [][]int
	m := make(map[[4]int]struct{})

	for i := range nums {
		for j := i + 1; j <= len(nums)-3; j++ {
			for k := j + 1; k <= len(nums)-2; k++ {
				for l := k + 1; l <= len(nums)-1; l++ {
					if nums[i]+nums[j]+nums[k]+nums[l] == target {
						s := []int{nums[i], nums[j], nums[k], nums[l]}
						sort.Sort(sort.IntSlice(s))
						a := [4]int{s[0], s[1], s[2], s[3]}
						if _, ok := m[a]; !ok {
							m[a] = struct{}{}
							result = append(result, s)
						}
					}
				}
			}
		}
	}
	return result
}

func main() {
	//固定测试用例
	s1 := []int{1, 0, -1, 0, -2, 2}
	t1 := 0
	a1 := fourSum(s1, t1)
	fmt.Println("数组", s1)
	fmt.Println("目标数", t1)
	fmt.Println("输出答案", a1)
	fmt.Println("正确答案[[-1 0 0 1] [-2 -1 1 2] [-2 0 0 2]]")
}
